home *** CD-ROM | disk | FTP | other *** search
/ HyperLib 1997 Winter - Disc 1 / HYPERLIB-1997-Winter-CD1.ISO.7z / HYPERLIB-1997-Winter-CD1.ISO / オンラインウェア / UTIL / PL 2.0 SupplementDoc Folder.sit / PL 2.0 SupplementDoc Folder / Documentation / Chapter 17. Arrays < prev    next >
Text File  |  1995-03-27  |  39KB  |  879 lines

  1. Common Lisp the Language, 2nd Edition
  2. -------------------------------------------------------------------------------
  3.  
  4. 17. Arrays
  5.  
  6. An array is an object with components arranged according to a rectilinear
  7. coordinate system. In principle, an array in Common Lisp may have any number of
  8. dimensions, including zero. (A zero-dimensional array has exactly one element.)
  9. In practice, an implementation may limit the number of dimensions supported,
  10. but every Common Lisp implementation must support arrays of up to seven
  11. dimensions. Each dimension is a non-negative integer; if any dimension of an
  12. array is zero, the array has no elements.
  13.  
  14. An array may be a general array, meaning each element may be any Lisp object,
  15. or it may be a specialized array, meaning that each element must be of a given
  16. restricted type.
  17.  
  18. [old_change_begin]
  19. One-dimensional arrays are called vectors. General vectors may contain any Lisp
  20. object. Vectors whose elements are restricted to type string-char are called
  21. strings. Vectors whose elements are restricted to type bit are called
  22. bit-vectors.
  23. [old_change_end]
  24.  
  25. [change_begin]
  26. X3J13 voted in March 1989 (CHARACTER-PROPOSAL)   to eliminate the type
  27. string-char and to redefine the type string to be the union of one or more
  28. specialized vector types, the types of whose elements are subtypes of the type
  29. character.
  30. [change_end]
  31.  
  32. -------------------------------------------------------------------------------
  33.  
  34.    *  Array Creation
  35.    *  Array Access
  36.    *  Array Information
  37.    *  Functions on Arrays of Bits
  38.    *  Fill Pointers
  39.    *  Changing the Dimensions of an Array
  40.  
  41. -------------------------------------------------------------------------------
  42.  
  43. 17.1. Array Creation
  44.  
  45. Do not be daunted by the many options of the function make-array. All that is
  46. required to construct an array is a list of the dimensions; most of the options
  47. are for relatively esoteric applications.
  48.  
  49. [Function]
  50. make-array dimensions &key :element-type :initial-element :initial-contents
  51. :adjustable :fill-pointer :displaced-to :displaced-index-offset
  52.  
  53. This is the primitive function for making arrays. The dimensions argument
  54. should be a list of non-negative integers that are to be the dimensions of the
  55. array; the length of the list will be the dimensionality of the array. Each
  56. dimension must be smaller than array-dimension-limit, and the product of all
  57. the dimensions must be smaller than array-total-size-limit. Note that if
  58. dimensions is nil, then a zero-dimensional array is created. For convenience
  59. when making a one-dimensional array, the single dimension may be provided as an
  60. integer rather than as a list of one integer.
  61.  
  62. An implementation of Common Lisp may impose a limit on the rank of an array,
  63. but this limit may not be smaller than 7. Therefore, any Common Lisp program
  64. may assume the use of arrays of rank 7 or less. The implementation-dependent
  65. limit on array rank is reflected in array-rank-limit.
  66.  
  67. The keyword arguments for make-array are as follows:
  68.  
  69. :element-type
  70.      This argument should be the name of the type of the elements of the array;
  71.      an array is constructed of the most specialized type that can nevertheless
  72.      accommodate elements of the given type. The type t specifies a general
  73.      array, one whose elements may be any Lisp object; this is the default
  74.      type.
  75.  
  76. [change_begin]
  77.  
  78.      X3J13 voted in January 1989 (ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS)   to
  79.      change typep and subtypep so that the specialized array type specifier
  80.      means the same thing for discrimination purposes as for declaration
  81.      purposes: it encompasses those arrays that can result by specifying
  82.      element-type as the element type to the function make-array. Therefore we
  83.      may say that if type is the :element-type argument, then the result will
  84.      be an array of type (array type); put another way, for any type A,
  85.  
  86.      (typep (make-array ... :element-type 'A ...)
  87.             '(array A)))
  88.  
  89.      is always true. See upgraded-array-element-type.
  90.  
  91. [change_end]
  92.  
  93. :initial-element
  94.      This argument may be used to initialize each element of the array. The
  95.      value must be of the type specified by the :element-type argument. If the
  96.      :initial-element option is omitted, the initial values of the array
  97.      elements are undefined (unless the :initial-contents or :displaced-to
  98.      option is used). The :initial-element option may not be used with the
  99.      :initial-contents or :displaced-to option.
  100.  
  101. :initial-contents
  102.      This argument may be used to initialize the contents of the array. The
  103.      value is a nested structure of sequences. If the array is
  104.      zero-dimensional, then the value specifies the single element. Otherwise,
  105.      the value must be a sequence whose length is equal to the first dimension;
  106.      each element must be a nested structure for an array whose dimensions are
  107.      the remaining dimensions, and so on. For example:
  108.  
  109.      (make-array '(4 2 3)
  110.                  :initial-contents
  111.                  '(((a b c) (1 2 3))
  112.                    ((d e f) (3 1 2))
  113.                    ((g h i) (2 3 1))
  114.                    ((j k l) (0 0 0))))
  115.  
  116.      The numbers of levels in the structure must equal the rank of the array.
  117.      Each leaf of the nested structure must be of the type specified by the
  118.      :type option. If the :initial-contents option is omitted, the initial
  119.      values of the array elements are undefined (unless the :initial-element or
  120.      :displaced-to option is used). The :initial-contents option may not be
  121.      used with the :initial-element or :displaced-to option.
  122.  
  123. :adjustable
  124.      This argument, if specified and not nil, indicates that it must be
  125.      possible to alter the array's size dynamically after it is created. This
  126.      argument defaults to nil.
  127.  
  128. [change_begin]
  129.  
  130.      X3J13 voted in June 1989 (ADJUST-ARRAY-NOT-ADJUSTABLE)   to clarify that
  131.      if this argument is non-nil then the predicate adjustable-array-p will
  132.      necessarily be true when applied to the resulting array; but if this
  133.      argument is nil (or omitted) then the resulting array may or may not be
  134.      adjustable, depending on the implementation, and therefore
  135.      adjustable-array-p may be correspondingly true or false of the resulting
  136.      array. Common Lisp provides no portable way to create a non-adjustable
  137.      array, that is, an array for which adjustable-array-p is guaranteed to be
  138.      false.
  139.  
  140. [change_end]
  141.  
  142. :fill-pointer
  143.      This argument specifies that the array should have a fill pointer. If this
  144.      option is specified and not nil, the array must be one-dimensional. The
  145.      value is used to initialize the fill pointer for the array. If the value t
  146.      is specified, the length of the array is used; otherwise the value must be
  147.      an integer between 0 (inclusive) and the length of the array (inclusive).
  148.      This argument defaults to nil.
  149.  
  150. :displaced-to
  151.      This argument, if specified and not nil, specifies that the array will be
  152.      a displaced array. The argument must then be an array; make-array will
  153.      create an indirect or shared array that shares its contents with the
  154.      specified array. In this case the :displaced-index-offset option may be
  155.      useful. It is an error if the array given as the :displaced-to argument
  156.      does not have the same :element-type as the array being created. The
  157.      :displaced-to option may not be used with the :initial-element or
  158.      :initial-contents option. This argument defaults to nil.
  159.  
  160. :displaced-index-offset
  161.      This argument may be used only in conjunction with the displaced-to
  162.      option. It must be a non-negative integer (it defaults to zero); it is
  163.      made to be the index-offset of the created shared array.
  164.  
  165.      When an array A is given as the :displaced-to argument to make-array when
  166.      creating array B, then array B is said to be displaced to array A. Now the
  167.      total number of elements in an array, called the total size of the array,
  168.      is calculated as the product of all the dimensions (see array-total-size).
  169.      It is required that the total size of A be no smaller than the sum of the
  170.      total size of B plus the offset n specified by the :displaced-index-offset
  171.      argument. The effect of displacing is that array B does not have any
  172.      elements of its own but instead maps accesses to itself into accesses to
  173.      array A. The mapping treats both arrays as if they were one-dimensional by
  174.      taking the elements in row-major order, and then maps an access to element
  175.      k of array B to an access to element k+n of array A.
  176.  
  177. If make-array is called with each of the :adjustable, :fill-pointer, and
  178. :displaced-to arguments either unspecified or nil, then the resulting array is
  179. guaranteed to be a simple array (see section 2.5).
  180.  
  181. [change_begin]
  182. X3J13 voted in June 1989 (ADJUST-ARRAY-NOT-ADJUSTABLE)   to clarify that if one
  183. or more of the :adjustable, :fill-pointer, and :displaced-to arguments is true,
  184. then whether the resulting array is simple is unspecified.
  185. [change_end]
  186.  
  187. Here are some examples of the use of make-array:
  188.  
  189. ;;; Create a one-dimensional array of five elements.
  190. (make-array 5)
  191.  
  192. ;;; Create a two-dimensional array, 3 by 4, with four-bit elements.
  193. (make-array '(3 4) :element-type '(mod 16))
  194.  
  195. ;;; Create an array of single-floats.
  196. (make-array 5 :element-type 'single-float))
  197.  
  198. ;;; Making a shared array.
  199. (setq a (make-array '(4 3)))
  200. (setq b (make-array 8 :displaced-to a
  201.                       :displaced-index-offset 2))
  202. ;;; Now it is the case that:
  203.         (aref b 0) == (aref a 0 2)
  204.         (aref b 1) == (aref a 1 0)
  205.         (aref b 2) == (aref a 1 1)
  206.         (aref b 3) == (aref a 1 2)
  207.         (aref b 4) == (aref a 2 0)
  208.         (aref b 5) == (aref a 2 1)
  209.         (aref b 6) == (aref a 2 2)
  210.         (aref b 7) == (aref a 3 0)
  211.  
  212. The last example depends on the fact that arrays are, in effect, stored in
  213. row-major order for purposes of sharing. Put another way, the indices for the
  214. elements of an array are ordered lexicographically.
  215.  
  216. -------------------------------------------------------------------------------
  217. Compatibility note: Both Lisp Machine Lisp, as described in reference [55], and
  218. Fortran [15,3] store arrays in column-major order.
  219. -------------------------------------------------------------------------------
  220.  
  221. [Constant]
  222. array-rank-limit
  223.  
  224. The value of array-rank-limit is a positive integer that is the upper exclusive
  225. bound on the rank of an array. This bound depends on the implementation but
  226. will not be smaller than 8; therefore every Common Lisp implementation supports
  227. arrays whose rank is between 0 and 7 (inclusive). (Implementors are encouraged
  228. to make this limit as large as practicable without sacrificing performance.)
  229.  
  230. [Constant]
  231. array-dimension-limit
  232.  
  233. The value of array-dimension-limit is a positive integer that is the upper
  234. exclusive bound on each individual dimension of an array. This bound depends on
  235. the implementation but will not be smaller than 1024. (Implementors are
  236. encouraged to make this limit as large as practicable without sacrificing
  237. performance.)
  238.  
  239. [change_begin]
  240. X3J13 voted in January 1989 (FIXNUM-NON-PORTABLE)   to specify that the value
  241. of array-dimension-limit must be of type fixnum. This in turn implies that all
  242. valid array indices will be fixnums.
  243. [change_end]
  244.  
  245. [Constant]
  246. array-total-size-limit
  247.  
  248. The value of array-total-size-limit is a positive integer that is the upper
  249. exclusive bound on the total number of elements in an array. This bound depends
  250. on the implementation but will not be smaller than 1024. (Implementors are
  251. encouraged to make this limit as large as practicable without sacrificing
  252. performance.)
  253.  
  254. The actual limit on array size imposed by the implementation may vary according
  255. to the :element-type of the array; in this case the value of
  256. array-total-size-limit will be the smallest of these individual limits.
  257.  
  258. [Function]
  259. vector &rest objects
  260.  
  261. The function vector is a convenient means for creating a simple general vector
  262. with specified initial contents. It is analogous to the function list.
  263.  
  264. (vector       ...   )
  265.    == (make-array (list n) :element-type t
  266.              :initial-contents (list       ...   ))
  267.  
  268. -------------------------------------------------------------------------------
  269.  
  270. 17.2. Array Access
  271.  
  272. The function aref is normally used for accessing an element of an array. Other
  273. access functions, such as svref, char, and bit, may be more efficient in
  274. specialized circumstances.
  275.  
  276. [Function]
  277. aref array &rest subscripts
  278.  
  279. This accesses and returns the element of array specified by the subscripts. The
  280. number of subscripts must equal the rank of the array, and each subscript must
  281. be a non-negative integer less than the corresponding array dimension.
  282.  
  283. aref is unusual among the functions that operate on arrays in that it
  284. completely ignores fill pointers. aref can access without error any array
  285. element, whether active or not. The generic sequence function elt, however,
  286. observes the fill pointer; accessing an element beyond the fill pointer with
  287. elt is an error.
  288.  
  289. [change_begin]
  290. Note that this remark, predating the design of the Common Lisp Object System,
  291. uses the term ``generic'' in a generic sense and not necessarily in the
  292. technical sense used by CLOS (see chapter 2).
  293. [change_end]
  294.  
  295. setf may be used with aref to destructively replace an array element with a new
  296. value.
  297.  
  298. Under some circumstances it is desirable to write code that will extract an
  299. element from an array a given a list z of the indices, in such a way that the
  300. code works regardless of the rank of the array. This is easy using apply:
  301.  
  302. (apply #'aref a z)
  303.  
  304. (The length of the list must of course equal the rank of the array.) This
  305. construction may be used with setf to alter the element so selected to some new
  306. value w:
  307.  
  308. (setf (apply #'aref a z) w)
  309.  
  310. [Function]
  311. svref simple-vector index
  312.  
  313. The first argument must be a simple general vector, that is, an object of type
  314. simple-vector. The element of the simple-vector specified by the integer index
  315. is returned.
  316.  
  317. The index must be non-negative and less than the length of the vector.
  318.  
  319. setf may be used with svref to destructively replace a simple-vector element
  320. with a new value.
  321.  
  322. svref is identical to aref except that it requires its first argument to be a
  323. simple vector. In some implementations of Common Lisp, svref may be faster than
  324. aref in situations where it is applicable. See also schar and sbit.
  325.  
  326. -------------------------------------------------------------------------------
  327.  
  328. 17.3. Array Information
  329.  
  330. The following functions extract from an array interesting information other
  331. than the elements.
  332.  
  333. [Function]
  334. array-element-type array
  335.  
  336. array-element-type returns a type specifier for the set of objects that can be
  337. stored in the array. This set may be larger than the set requested when the
  338. array was created; for example, the result of
  339.  
  340. (array-element-type (make-array 5 :element-type '(mod 5)))
  341.  
  342. could be (mod 5), (mod 8), fixnum, t, or any other type of which (mod 5) is a
  343. subtype. See subtypep.
  344.  
  345. [Function]
  346. array-rank array
  347.  
  348. This returns the number of dimensions (axes) of array. This will be a
  349. non-negative integer. See array-rank-limit.
  350.  
  351. -------------------------------------------------------------------------------
  352. Compatibility note: In Lisp Machine Lisp, this is called array-#-dims. This
  353. name causes problems in other Lisp dialects because of the # character.
  354. -------------------------------------------------------------------------------
  355.  
  356. [Function]
  357. array-dimension array axis-number
  358.  
  359. The length of dimension number axis-number of the array is returned. array may
  360. be any kind of array, and axis-number should be a non-negative integer less
  361. than the rank of array. If the array is a vector with a fill pointer,
  362. array-dimension returns the total size of the vector, including inactive
  363. elements, not the size indicated by the fill pointer. (The function length will
  364. return the size indicated by the fill pointer.)
  365.  
  366. -------------------------------------------------------------------------------
  367. Compatibility note: This is similar to the Lisp Machine Lisp function
  368. array-dimension-n, but takes its arguments in the other order, and is
  369. zero-origin for consistency instead of one-origin. In Lisp Machine Lisp
  370. (array-dimension-n 0) returns the length of the array leader.
  371. -------------------------------------------------------------------------------
  372.  
  373. [Function]
  374. array-dimensions array
  375.  
  376. array-dimensions returns a list whose elements are the dimensions of array.
  377.  
  378. [Function]
  379. array-total-size array
  380.  
  381. array-total-size returns the total number of elements in the array, calculated
  382. as the product of all the dimensions.
  383.  
  384. (array-total-size x)
  385.    == (apply #'* (array-dimensions x))
  386.    == (reduce #'* (array-dimensions x))
  387.  
  388. Note that the total size of a zero-dimensional array is 1. The total size of a
  389. one-dimensional array is calculated without regard for any fill pointer.
  390.  
  391. [Function]
  392. array-in-bounds-p array &rest subscripts
  393.  
  394. This predicate checks whether the subscripts are all legal subscripts for
  395. array. The predicate is true if they are all legal; otherwise it is false. The
  396. subscripts must be integers. The number of subscripts supplied must equal the
  397. rank of the array. Like aref, array-in-bounds-p ignores fill pointers.
  398.  
  399. [Function]
  400. array-row-major-index array &rest subscripts
  401.  
  402. This function takes an array and valid subscripts for the array and returns a
  403. single non-negative integer less than the total size of the array that
  404. identifies the accessed element in the row-major ordering of the elements. The
  405. number of subscripts supplied must equal the rank of the array. Each subscript
  406. must be a non-negative integer less than the corresponding array dimension.
  407. Like aref, array-row-major-index ignores fill pointers.
  408.  
  409. A possible definition of array-row-major-index, with no error checking, would
  410. be
  411.  
  412. (defun array-row-major-index (a &rest subscripts)
  413.   (apply #'+ (maplist #'(lambda (x y)
  414.                           (* (car x) (apply #'* (cdr y))))
  415.                       subscripts
  416.                       (array-dimensions a))))
  417.  
  418. For a one-dimensional array, the result of array-row-major-index always equals
  419. the supplied subscript.
  420.  
  421. [change_begin]
  422.  
  423. [Function]
  424. row-major-aref array index
  425.  
  426. X3J13 voted in March 1988 (AREF-1D)   to add the function row-major-aref. This
  427. allows any array element to be accessed as if the containing array were
  428. one-dimensional. The index must be a non-negative integer less than the total
  429. size of the array. It indexes into the array as if its elements were arranged
  430. one-dimensionally in row-major order. It may be understood in terms of aref as
  431. follows:
  432.  
  433. (row-major-aref array index) ==
  434.   (aref (make-array (array-total-size array))
  435.                     :displaced-to array
  436.                     :element-type (array-element-type array))
  437.         index)
  438.  
  439. In other words, one may treat an array as one-dimensional by creating a new
  440. one-dimensional array that is displaced to the old one and then accessing the
  441. new array. Alternatively, aref may be understood in terms of row-major-aref:
  442.  
  443. (aref array       ...   ) ==
  444.   (row-major-aref array
  445.                   (array-row-major-index array       ...   )
  446.  
  447. That is, a multidimensional array access is equivalent to a row-major access
  448. using an equivalent row-major index.
  449.  
  450. Like aref, row-major-aref completely ignores fill pointers. A call to
  451. row-major-setf is suitable for use as a place for setf.
  452.  
  453. This operation makes it easier to write code that efficiently processes arrays
  454. of any rank. Suppose, for example, that one wishes to set every element of an
  455. array tennis-scores to zero. One might write
  456.  
  457. (fill (make-array (array-total-size tennis-scores)
  458.                   :element-type (array-element-type tennis-scores)
  459.                   :displaced-to tennis-scores)
  460.       0)
  461.  
  462. Unfortunately, this incurs the overhead of creating a displaced array, and fill
  463. cannot be applied to multidimensional arrays. Another approach would be to
  464. handle each possible rank separately:
  465.  
  466. (ecase (array-rank tennis-scores)
  467.   (0 (setf (aref tennis-scores) 0))
  468.   (1 (dotimes (i0 (array-dimension tennis-scores 0))
  469.        (setf (aref tennis-scores i0) 0)))
  470.   (2 (dotimes (i0 (array-dimension tennis-scores 0))
  471.        (dotimes (i1 (array-dimension tennis-scores 1))
  472.          (setf (aref tennis-scores i0 i1) 0))))
  473.   ...
  474.   (7 (dotimes (i0 (array-dimension tennis-scores 0))
  475.        (dotimes (i1 (array-dimension tennis-scores 1))
  476.          (dotimes (i2 (array-dimension tennis-scores 1))
  477.            (dotimes (i3 (array-dimension tennis-scores 1))
  478.              (dotimes (i4 (array-dimension tennis-scores 1))
  479.                (dotimes (i5 (array-dimension tennis-scores 1))
  480.                  (dotimes (i6 (array-dimension tennis-scores 1))
  481.                    (setf (aref tennis-scores i0 i1 i2 i3 i4 i5 i6)
  482.                          0)))))))))
  483.   )
  484.  
  485. It is easy to get tired of writing such code. Furthermore, this approach is
  486. undesirable because some implementations of Common Lisp will in fact correctly
  487. support arrays of rank greater than 7 (though no implementation is required to
  488. do so). A recursively nested loop does the job, but it is still pretty hairy:
  489.  
  490. (labels
  491.   ((grok-any-rank (&rest indices)
  492.      (let ((d (- (array-rank tennis-scores) (length indices)))
  493.        (if (= d 0)
  494.            (setf (apply #'row-major-aref indices) 0)
  495.            (dotimes (i (array-dimension tennis-scores (- d 1)))
  496.              (apply #'grok-any-rank i indices))))))
  497.   (grok-any-rank))
  498.  
  499. Whether this code is particularly efficient depends on many implementation
  500. parameters, such as how &rest arguments are handled and how cleverly calls to
  501. apply are compiled. How much easier it is to use row-major-aref!
  502.  
  503. (dotimes (i (array-total-size tennis-scores))
  504.   (setf (row-major-aref tennis-scores i) 0))
  505.  
  506. Surely this code is sweeter than the honeycomb.
  507. [change_end]
  508.  
  509. [Function]
  510. adjustable-array-p array
  511.  
  512. This predicate is true if the argument (which must be an array) is adjustable,
  513. and otherwise is false.
  514.  
  515. [change_begin]
  516. X3J13 voted in June 1989 (ADJUST-ARRAY-NOT-ADJUSTABLE)   to clarify that
  517. adjustable-array-p is true of an array if and only if adjust-array, when
  518. applied to that array, will return the same array, that is, an array eq to the
  519. original array. If the :adjustable argument to make-array is non-nil when an
  520. array is created, then adjustable-array-p must be true of that array. If an
  521. array is created with the :adjustable argument nil (or omitted), then
  522. adjustable-array-p may be true or false of that array, depending on the
  523. implementation. X3J13 further voted to define the terminology ``adjustable
  524. array'' to mean precisely ``an array of which adjustable-array-p is true.'' See
  525. make-array and adjust-array.
  526. [change_end]
  527.  
  528. -------------------------------------------------------------------------------
  529.  
  530. 17.4. Functions on Arrays of Bits
  531.  
  532. The functions described in this section operate only on arrays of bits, that
  533. is, specialized arrays whose elements are all 0 or 1.
  534.  
  535. [Function]
  536. bit bit-array &rest subscripts
  537. sbit simple-bit-array &rest subscripts
  538.  
  539. bit is exactly like aref but requires an array of bits, that is, one of type
  540. (array bit). The result will always be 0 or 1. sbit is like bit but
  541. additionally requires that the first argument be a simple array (see section
  542. 2.5). Note that bit and sbit, unlike char and schar, allow the first argument
  543. to be an array of any rank.
  544.  
  545. setf may be used with bit or sbit to destructively replace a bit-array element
  546. with a new value.
  547.  
  548. bit and sbit are identical to aref except for the more specific type
  549. requirements on the first argument. In some implementations of Common Lisp, bit
  550. may be faster than aref in situations where it is applicable, and sbit may
  551. similarly be faster than bit.
  552.  
  553. [Function]
  554.  
  555. bit-and bit-array1 bit-array2 &optional result-bit-array
  556. bit-ior bit-array1 bit-array2 &optional result-bit-array
  557. bit-xor bit-array1 bit-array2 &optional result-bit-array
  558. bit-eqv bit-array1 bit-array2 &optional result-bit-array
  559. bit-nand bit-array1 bit-array2 &optional result-bit-array
  560. bit-nor bit-array1 bit-array2 &optional result-bit-array
  561. bit-andc1 bit-array1 bit-array2 &optional result-bit-array
  562. bit-andc2 bit-array1 bit-array2 &optional result-bit-array
  563. bit-orc1 bit-array1 bit-array2 &optional result-bit-array
  564. bit-orc2 bit-array1  bit-array2 &optional result-bit-array
  565.  
  566. These functions perform bit-wise logical operations on bit-arrays. All of the
  567. arguments to any of these functions must be bit-arrays of the same rank and
  568. dimensions. The result is a bit-array of matching rank and dimensions, such
  569. that any given bit of the result is produced by operating on corresponding bits
  570. from each of the arguments.
  571.  
  572. If the third argument is nil or omitted, a new array is created to contain the
  573. result. If the third argument is a bit-array, the result is destructively
  574. placed into that array. If the third argument is t, then the first argument is
  575. also used as the third argument; that is, the result is placed back in the
  576. first array.
  577.  
  578. The following table indicates what the result bit is for each operation as a
  579. function of the two corresponding argument bits.
  580.  
  581. argument1  0  0  1  1
  582. argument2  0  1  0  1  Operation name
  583. ------------------------------------------------------------
  584. bit-and    0  0  0  1  and
  585. bit-ior    0  1  1  1  inclusive or
  586. bit-xor    0  1  1  0  exclusive or
  587. bit-eqv    1  0  0  1  equivalence (exclusive nor)
  588. bit-nand   1  1  1  0  not-and
  589. bit-nor    1  0  0  0  not-or
  590. bit-andc1  0  1  0  0  and complement of argument1 with argument2
  591. bit-andc2  0  0  1  0  and argument1 with complement of argument2
  592. bit-orc1   1  1  0  1  or complement of argument1 with argument2
  593. bit-orc2   1  0  1  1  or argument1 with complement of argument2
  594. ------------------------------------------------------------
  595.  
  596. For example:
  597.  
  598. (bit-and #*1100 #*1010) => #*1000
  599. (bit-xor #*1100 #*1010) => #*0110
  600. (bit-andc1 #*1100 #*1010) => #*0100
  601.  
  602. See logand and related functions.
  603.  
  604. [Function]
  605. bit-not bit-array &optional result-bit-array
  606.  
  607. The first argument must be an array of bits. A bit-array of matching rank and
  608. dimensions is returned that contains a copy of the argument with all the bits
  609. inverted. See lognot.
  610.  
  611. If the second argument is nil or omitted, a new array is created to contain the
  612. result. If the second argument is a bit-array, the result is destructively
  613. placed into that array. If the second argument is t, then the first argument is
  614. also used as the second argument; that is, the result is placed back in the
  615. first array.
  616.  
  617. -------------------------------------------------------------------------------
  618.  
  619. 17.5. Fill Pointers
  620.  
  621. Several functions for manipulating a fill pointer are provided in Common Lisp
  622. to make it easy to incrementally fill in the contents of a vector and, more
  623. generally, to allow efficient varying of the length of a vector. For example, a
  624. string with a fill pointer has most of the characteristics of a PL/I varying
  625. string.
  626.  
  627. The fill pointer is a non-negative integer no larger than the total number of
  628. elements in the vector (as returned by array-dimension); it is the number of
  629. ``active'' or ``filled-in'' elements in the vector. The fill pointer
  630. constitutes the ``active length'' of the vector; all vector elements whose
  631. index is less than the fill pointer are active, and the others are inactive.
  632. Nearly all functions that operate on the contents of a vector will operate only
  633. on the active elements. An important exception is aref, which can be used to
  634. access any vector element whether in the active region of the vector or not. It
  635. is important to note that vector elements not in the active region are still
  636. considered part of the vector.
  637.  
  638. -------------------------------------------------------------------------------
  639. Implementation note: An implication of this rule is that vector elements
  640. outside the active region may not be garbage-collected.
  641. -------------------------------------------------------------------------------
  642.  
  643. Only vectors (one-dimensional arrays) may have fill pointers; multidimensional
  644. arrays may not. (Note, however, that one can create a multidimensional array
  645. that is displaced to a vector that has a fill pointer.)
  646.  
  647. [Function]
  648. array-has-fill-pointer-p array
  649.  
  650. The argument must be an array. array-has-fill-pointer-p returns t if the array
  651. has a fill pointer, and otherwise returns nil. Note that
  652. array-has-fill-pointer-p always returns nil if the array is not
  653. one-dimensional.
  654.  
  655. [Function]
  656. fill-pointer vector
  657.  
  658. The fill pointer of vector is returned. It is an error if the vector does not
  659. have a fill pointer.
  660.  
  661. setf may be used with fill-pointer to change the fill pointer of a vector. The
  662. fill pointer of a vector must always be an integer between zero and the size of
  663. the vector (inclusive).
  664.  
  665. [Function]
  666. vector-push new-element vector
  667.  
  668. vector must be a one-dimensional array that has a fill pointer, and new-element
  669. may be any object. vector-push attempts to store new-element in the element of
  670. the vector designated by the fill pointer, and to increase the fill pointer by
  671. 1. If the fill pointer does not designate an element of the vector
  672. (specifically, when it gets too big), it is unaffected and vector-push returns
  673. nil. Otherwise, the store and increment take place and vector-push returns the
  674. former value of the fill pointer (1 less than the one it leaves in the vector);
  675. thus the value of vector-push is the index of the new element pushed.
  676.  
  677. [change_begin]
  678. It is instructive to compare vector-push, which is a function, with push, which
  679. is a macro that requires a place suitable for setf. A vector with a fill
  680. pointer effectively contains the place to be modified in its fill-pointer slot.
  681.  
  682. [change_end]
  683.  
  684. [Function]
  685. vector-push-extend new-element vector &optional extension
  686.  
  687. vector-push-extend is just like vector-push except that if the fill pointer
  688. gets too large, the vector is extended (using adjust-array) so that it can
  689. contain more elements. If, however, the vector is not adjustable, then
  690. vector-push-extend signals an error.
  691.  
  692. [change_begin]
  693. X3J13 voted in June 1989 (ADJUST-ARRAY-NOT-ADJUSTABLE)   to clarify that
  694. vector-push-extend regards an array as not adjustable if and only if
  695. adjustable-array-p is false of that array.
  696. [change_end]
  697.  
  698. The optional argument extension, which must be a positive integer, is the
  699. minimum number of elements to be added to the vector if it must be extended; it
  700. defaults to a ``reasonable'' implementation-dependent value.
  701.  
  702. [Function]
  703. vector-pop vector
  704.  
  705. vector must be a one-dimensional array that has a fill pointer. If the fill
  706. pointer is zero, vector-pop signals an error. Otherwise the fill pointer is
  707. decreased by 1, and the vector element designated by the new value of the fill
  708. pointer is returned.
  709.  
  710. -------------------------------------------------------------------------------
  711.  
  712. 17.6. Changing the Dimensions of an Array
  713.  
  714. This function may be used to resize or reshape an array. Its options are
  715. similar to those of make-array.
  716.  
  717. [Function]
  718. adjust-array array new-dimensions &key :element-type :initial-element
  719. :initial-contents :fill-pointer :displaced-to :displaced-index-offset
  720.  
  721. adjust-array takes an array and a number of other arguments as for make-array.
  722. The number of dimensions specified by new-dimensions must equal the rank of
  723. array.
  724.  
  725. adjust-array returns an array of the same type and rank as array, with the
  726. specified new-dimensions. In effect, the array argument itself is modified to
  727. conform to the new specifications, but this may be achieved either by modifying
  728. the array or by creating a new array and modifying the array argument to be
  729. displaced to the new array.
  730.  
  731. In the simplest case, one specifies only the new-dimensions and possibly an
  732. :initial-element argument. Those elements of array that are still in bounds
  733. appear in the new array. The elements of the new array that are not in the
  734. bounds of array are initialized to the :initial-element; if this argument is
  735. not provided, then the initial contents of any new elements are undefined.
  736.  
  737. If :element-type is specified, then array must be such that it could have been
  738. originally created with that type; otherwise an error is signaled. Specifying
  739. :element-type to adjust-array serves only to require such an error check.
  740.  
  741. If :initial-contents or :displaced-to is specified, then it is treated as for
  742. make-array. In this case none of the original contents of array appears in the
  743. new array.
  744.  
  745. If :fill-pointer is specified, the fill pointer of the array is reset as
  746. specified. An error is signaled if array had no fill pointer already.
  747.  
  748. [change_begin]
  749. X3J13 voted in June 1988 (ADJUST-ARRAY-FILL-POINTER)   to clarify the treatment
  750. of the :fill-pointer argument as follows.
  751.  
  752. If the :fill-pointer argument is not supplied, then the fill pointer of the
  753. array is left alone. It is an error to try to adjust the array to a total size
  754. that is smaller than its fill pointer.
  755.  
  756. If the :fill-pointer argument is supplied, then its value must be either an
  757. integer, t, or nil. If it is an integer, then it is the new value for the fill
  758. pointer; it must be non-negative and no greater than the new size to which the
  759. array is being adjusted. If it is t, then the fill pointer is set equal to the
  760. new size for the array. If it is nil, then the fill pointer is left alone; it
  761. is as if the argument had not been supplied. Again, it is an error to try to
  762. adjust the array to a total size that is smaller than its fill pointer.
  763.  
  764. An error is signaled if a non-nil :fill-pointer value is supplied and the array
  765. to be adjusted does not already have a fill pointer.
  766.  
  767. This extended treatment of the :fill-pointer argument to adjust-array is
  768. consistent with the previously existing treatment of the :fill-pointer argument
  769. to make-array.
  770. [change_end]
  771.  
  772. adjust-array may, depending on the implementation and the arguments, simply
  773. alter the given array or create and return a new one. In the latter case the
  774. given array will be altered so as to be displaced to the new array and have the
  775. given new dimensions.
  776.  
  777. [old_change_begin]
  778. It is not permitted to call adjust-array on an array that was not created with
  779. the :adjustable option. The predicate adjustable-array-p may be used to
  780. determine whether or not an array is adjustable.
  781. [old_change_end]
  782.  
  783. [change_begin]
  784. X3J13 voted in January 1989 (ADJUST-ARRAY-NOT-ADJUSTABLE)   to allow
  785. adjust-array to be applied to any array. If adjust-array is applied to an array
  786. that was originally created with :adjustable true, the array returned is eq to
  787. its first argument. It is not specified whether adjust-array returns an array
  788. eq to its first argument for any other arrays. If the array returned by
  789. adjust-array is not eq to its first argument, the original array is unchanged
  790. and does not share storage with the new array.
  791.  
  792. Under this new definition, it is wise to treat adjust-array in the same manner
  793. as delete and nconc: one should carefully retain the returned value, for
  794. example by writing
  795.  
  796. (setq my-array (adjust-array my-array ...))
  797.  
  798. rather than relying solely on a side effect.
  799. [change_end]
  800.  
  801. If adjust-array is applied to an array that is displaced to another array x,
  802. then afterwards neither array nor the returned result is displaced to x unless
  803. such displacement is explicitly re-specified in the call to adjust-array.
  804.  
  805. For example, suppose that the 4-by-4 array m looks like this:
  806.  
  807. #2A( ( alpha     beta      gamma     delta )
  808.      ( epsilon   zeta      eta       theta )
  809.      ( iota      kappa     lambda    mu    )
  810.      ( nu        xi        omicron   pi    ) )
  811.  
  812. Then the result of
  813.  
  814. (adjust-array m '(3 5) :initial-element 'baz)
  815.  
  816. is a 3-by-5 array with contents
  817.  
  818. #2A( ( alpha     beta      gamma     delta     baz )
  819.      ( epsilon   zeta      eta       theta     baz )
  820.      ( iota      kappa     lambda    mu        baz ) )
  821.  
  822. Note that if array a is created displaced to array b and subsequently array b
  823. is given to adjust-array, array a will still be displaced to array b; the
  824. effects of this displacement and the rule of row-major storage order must be
  825. taken into account.
  826.  
  827. [change_begin]
  828. X3J13 voted in June 1988 (ADJUST-ARRAY-DISPLACEMENT)   to clarify the
  829. interaction of adjust-array with array displacement.
  830.  
  831. Suppose that an array A is to be adjusted. There are four cases according to
  832. whether or not A was displaced before adjustment and whether or not the result
  833. is displaced after adjustment.
  834.  
  835.    *  Suppose A is not displaced either before or after. The dimensions of A
  836.      are altered, and the contents are rearranged as appropriate. Additional
  837.      elements of A are taken from the :initial-element argument. However, the
  838.      use of the :initial-contents argument causes all old contents to be
  839.      discarded.
  840.  
  841.    *  Suppose A is not displaced before, but is displaced to array C after.
  842.      None of the original contents of A appears in A afterwards; A now contains
  843.      (some of) the contents of C, without any rearrangement of C.
  844.  
  845.    *  Suppose A is displaced to array B before the call, and is displaced to
  846.      array C after the call. (Note that B and C may be the same array.) The
  847.      contents of B do not appear in A afterwards (unless such contents also
  848.      happen to be in C, as when B and C are the same, for example). If
  849.      :displaced-index-offset is not specified in the call to adjust-array, it
  850.      defaults to zero; the old offset (into B) is not retained.
  851.  
  852.    *  Suppose A is displaced to array B before the call, but is not displaced
  853.      afterwards. In this case A gets a new ``data region'' and (some of) the
  854.      contents of B are copied into it as appropriate to maintain the existing
  855.      old contents. Additional elements of A are taken from the :initial-element
  856.      argument. However, the use of the :initial-contents argument causes all
  857.      old contents to be discarded.
  858.  
  859. If array X is displaced to array Y, and array Y is displaced to array Z, and
  860. array Y is altered by adjust-array, array X must now refer to the adjusted
  861. contents of Y. This means that an implementation may not collapse the chain to
  862. make X refer to Z directly and forget that the chain of reference passes
  863. through array Y. (Caching techniques are of course permitted, as long as they
  864. preserve the semantics specified here.)
  865.  
  866. If X is displaced to Y, it is an error to adjust Y in such a way that it no
  867. longer has enough elements to satisfy X. This error may be signaled at the time
  868. of the adjustment, but this is not required.
  869.  
  870. Note that omitting the :displaced-to argument to adjust-array is equivalent to
  871. specifying :displaced-to nil; in either case, the array is not displaced after
  872. the call regardless of whether it was displaced before the call.
  873. [change_end]
  874.  
  875. -------------------------------------------------------------------------------
  876.  
  877.  
  878.  
  879.